package dp.combinationSum4;

import java.util.Arrays;

/**
 * @Date 2020/04/23
 * @author 王光浩
 * @Thinking 使用递归
		递归参数：int index（当前所代表的下标），int[] nums（正整数数组），int left（剩下的值）
		basic case：如果 index<0 return 0  ; 如果 left==0 return 1;
		主体：
			如果 left<nums[index],继续递归将 index--;
			设置一个计数器count统计返回值（count初始值为0）
			进入循环，循环的结束条件时nums[index]*n>left（其中n代表循环次数,初始值为1）
			在循环内部 count += 递归方法（index-1，nums,left-nums[index]*n）
			最后 return count。
 */
public class MyMethodOne {
	public int combinationSum4(int[] nums, int target) {
		Arrays.sort(nums);
		int count =0;
		for(int i=0 ; i<nums.length ; i++) {
			count += helper(nums.length-1,nums,target);
		}
		return count;
    }
	private int helper(int index,int[] nums,int left) {
		if( left<0 ) return 0;
		if( left==0 ) return 1;
		if( index<0 ) return 0;  //该个组合不能形成 target
		if( nums[index]>left ) return helper(index--,nums,left);
		int count = 0;
		long n =nums[index];
		while( n<=left ) {
			count += helper(index-1,nums,(int)(left-n));
			n += nums[index];
		}
		return count;
	}
}
